// 散列
// 链表的增删操作很快，但查找很慢，而数组的查找很快，但增删操作很慢
// 数组的索引就能快速定位到与之对应的元素
// 设法将一个字符串通过某种算法转换成一个数字，并且数字位于某个可接受的范围（目的是让底层的数组不会过长，比如我们要添加80个数，那么转换成的索引值就不能大于80）
// 于增删问题，我们则可以在元素的位置上放入一个够短的链表，这样就能利用其操作很快这个优点


// 4.2　散列函数
// 散列函数是一个一一对应的函数，则在查找时，只需要根据散列函数对给定关键字的某种运算得到待查找结点的存储位置，无须进行比较。
//一般情况下，散列表的空间要比结点的集合大，虽然这浪费了一部分空间，
//但是提高了查找效率。散列表空间为m，填入表中的结点数为n，则比值n/m称为散列表的装填因子（装填因子表示散列表中元素的填满程度）。
//装填因子越大，填满的元素越多，反之填满的元素越少，其取值范围一般为0.65~0.9。

// 散列函数应当尽量简单，其值域必须在表长的范围之内，尽量不要产生“冲突

// 散列函数的构造方法

// 直接地址法
// 为hash(K)=aK+C。其优点是不会产生冲突，缺点是空间复杂度可能会较高，适用于元素较少的情况

// 除留余数法
// 将数据元素关键字除以某个常数所留的余数作为散列地址，该方法计算简单，适用范围广，是经常使用的一种散列函数，
// 可以表示为：hash(K)=K mod C。

// 数字分析法
// 该方法取数据元素关键字中某些取值较均匀的数字来作为散列地址，这样可以尽量避免冲突，
// 但是该方法只适合于所有关键字已知的情况

// 平方求和法：
// 将当前字符串转化为Unicode值，并求出这个值的平方，取平方值中间的几位作为当前数字的散列值，具体取几位要取决于当前散列表的大小。

// 分段求和法：
// 根据当前散列表的位数把所要插入的数值分成若干段，把若干段进行相加，
// 舍去最高位后的结果就是这个散列表的散列值。

class Hash {
    constructor() {
      this.table = new Array(1000);
    }
    hash(data) {
      let total = 0;
      for (let i = 0; i < data.length; i++) {
        total += data.charCodeAt(i);
      }
      // 把字符串转化为Unicode之后进行求和，再进行平方运算
      let s = total * total + "";
      // 保留中间2位
      let index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1;
      console.log("Hash Value: " + data + " -> " + index);
      return index;
    }
    insert(key, data) {
      let index = this.hash(key);
      // 把中间位置的数当作散列表的索引
      this.table[index] = {
        name: key,
        data: data,
      }
    }
    get(key) {
      let index = this.hash(key);
      let node = this.table[index];
      return node && node.data;
    }
    forEach(cb) {
      for (let i = 0; i < this.table.length; i++) {
        let node = this.table[i];
        if (node) {
          cb(node.data, node.name);
        }
      }
    }
  }
  let someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
  let hash = new Hash();
  for (let i = 0; i < someNames.length; ++i) {
    hash.insert(someNames[i], someNames[i]);
  }
  
  hash.forEach(function(el, i) {
    console.log(el, i);
  });


//   4.3　散列冲突的解决方案

// 在构造散列表时，存在这样的问题：对于两个不同的关键字，通过我们的散列函数计算散列地址时却得到了相同的结果，我们将这种现象称为散列冲突
// 解决冲突的技术可以分为两类：开散列方法（open hashing）和闭散列方法（closed hashing）。
// 开散列方法是将冲突记录在表外，
// 而闭散列方法是将冲突记录在表内的另一个位置上


// 4.3.1　开散列方法
// 开散列方法最著名的实现是拉链法
// 它把散列中的每个槽（底层数组的元素）定义为一个链表的表头
// 它把散列中的每个槽（底层数组的元素）定义为一个链表的表头。
// 散列到一个特定槽的所有记录都放到这个槽的链表中。
// 我们在添加元素时，通过散列函数计算出索引值，然后判定它是否为空，
// 不为空则遍历链表检查是否已经保存相同的值。否则就创建一个新结点，
// 将其插入到数组上，原链表则作为跟班挂在它的next属性中。删除时，
// 为了方便，就直接将链表的data属性重置为null。

class Node {
    constructor(name, data) {
      this.name = name;
      this.data = data;
      this.next = null;
    }
  }
  class Hash {
    constructor() {
      this.table = [];
    }
    hash(key) {
      key += ""; // 强制转化字符串
      let HASHSIZE = 100;
      let h = 0;
      for (let i = 0; i < key.length; i++) {
        h = key.charCodeAt(i) + h * 31;
      }
      // 将整个字符串按照特定关系转化为一个整数，然后对散列长度取余
      return h % HASHSIZE;
    }
    loopup(key) {
      let hashvalue = this.hash(key);
      let node = this.table[hashvalue];
      while (node) {
        if (node.name == key + "") {
          return node;
        }
        node = node.next;
      }
    }
    get(key) {
      let node = this.loopup(key);
      return (node && node.data !== null) ? node.data : null;
    }
    remove(key) {
      let node = this.loopup(key);
      if (node) {
        node.data = null;
      }
    }
    insert(key, data) {
      let hashvalue = this.hash(key);
      // 头插法，不管该散列位置有没有其他结点，直接插入结点
      let node = this.table[hashvalue];
      let next = node;
      if (node) {
        do {
          if (node.name === key+"") {
            node.data = data;
            return; // key、data一致
          }
        } while (node = node.next);
      }
      let np = new Node(key, data);
      this.table[hashvalue] = np;
      np.next = next;
    }
    forEach(cb) {
      for (let i = 0; i < 100; i++) {// HASHSIZE = 100
        if (this.table[i]) {
          let link = this.table[i];
          while (link) {
              if (link.data !== null) {cb(link.name, link.data);
            }
            link = link.next;
          }
        }
      }
    }
  }
  
  let names = ["First Name", "Last Name", "address", "phone", "k101", "k110"];
  let descs = ["Kobe", "Bryant", "USA", "26300788", "Value1", "Value2"];
  let hash = new Hash();
  for (let i = 0; i < 6; ++i) {
    hash.insert(names[i], descs[i]);
  }
  console.log("we should see ", hash.get("k110"));
  hash.insert("phone", "9433120451"); // 这里计算的散列是冲突的，是为了测试冲突情况下的插入
  console.log("we have ", hash.get("k101"), "and", hash.get("phone"));



//   4.3.2　闭散列方法

// 线性探测：当不同的key值通过散列函数映射到同一散列地址上时，检测当前地址的下一个地址是否可以插入，如果可以的话，就存储在当前位置的下一个地址，否则，继续向下一个地址寻找

// 二次探测：这是对线性探测的一种改进，进行线性探测后插入的key值太集中，这样会造成key值通过散列函数后还是无法正确映射到地址上，
// 也会造成查找、删除时的效率低下。因此，通过二次探测的方法，取当前地址加上i^2，可以取到的新地址，使key值稍微分散开

// 线性探测不如二次探测，因为线性探测最后会导致索引值都聚集在了一起
// （这在数学上叫基本聚集），数据量大了，探测次数会越来越多。另一种解决基本取集的方法是伪随机探查。

// 伪随机探查：在伪随机探查中，探查序列中的第 i 个槽是 (h(k) + ri) mod M，ri是 1 到 M1 之间数的随机序列。
// 所有的插入和检索都使用相同的伪随机序列

// 尽管二次探测和伪随机探查能够解决基本聚集问题，然而如果散列函数在某个基槽聚集，依然会保持聚集状态。
// 这个问题称为二次聚集（secondary clustering）。要解决二次聚集问题，可以使用双散列方法


// 双散列方法的形式：
function hash1( key,  i){
  return i*hash2(key);
}

// 好的双散列实现方法应当保证所有探查序列常数都与表长度M互素。
// 其中一种方法是设置 M 为素数，而h2 返回[1, M1]中的值。另外一种方法是给定一个 m 值，设置 M = 2m，然后让 h2 返回 1 到 2m 之间的一个奇数值。

// 闭散列方法结论：
// 每个新插入操作产生的额外查找代价将在散列表接近半满时急剧增加。
// 如果还考虑到访问模式，在理想情况下，记录应当沿着探查序列按照访问频率排序。

class Node {
    constructor(name, data) {
      this.name = name;
      this.data = data;
      this.next = null;
      this.state = true;
    }
  }
  class Hash {
    constructor() {
      this.table = [];
      this.capacity = 100; // 容量
      this.length = 0;
    }
    hash(s) {
  
      let seed = 131; // 31 131 1313 13131 131313 etc..
      let hash = 0;
      for (let i = 0; i < s.length; i++) {
        hash = s.charCodeAt(i) + hash * seed;
      }
      return (hash & 0x7FFFFFFF);
    }
    getHash(key, capacity) {
      return this.hash(key + "") % capacity;
    }
    size() {
      return this.length;
    }
    insert(key, value) {
      let inserted = false;
      let index = this.find(key, function(item) {
        item.data = value;
        if (!item.state) {
          this.length++;
        }
        inserted = item.state = true;
      });
      if (!inserted) {
        this.table[index] = new Node(key, value);
        this.length++;
      }
      if (this.length * 10 / this.capacity > 6) {
        this.capacity *= 2;
      }
      return true;
    }
  
    find(key, cb) {
      let index = this.getHash(key, this.capacity),
        i = 1,
        table = this.table;
      while (table[index]) {
        if (table[index].name === key + "") {
          cb.call(this, table[index]);
        }
        index = index + 2 * i - 1;
        index %= this.capacity;
        i++;
      }
      return index;
    }
    get(key) {
      let value = null;
      this.find(key, function(item) {
        if (item.state) {
          value = item.data;
        }
      });
      return value;
    }
    remove(key) {
      let oldSize = this.length;
      let index = this.find(key, function(item) {
        item.state = false;
        this.length--;
        if (this.length * 10 / this.capacity < 6) {
          this.capacity /= 2;
        }
      });
      return this.length !== oldSize;
    }
    forEach(cb) {
      for (let i = 0, n = this.capacity; i < n; i++) {
        let el = this.table[i];
        if (el && el.state) {
          cb(el.name, el.data);
        }
      }
    }
  }
  let names = ["First Name", "Last Name", "address", "phone", "k101", "k110"];
  let descs = ["Kobe", "Bryant", "USA", "26300788", "Value1", "Value2"];
  let hash = new Hash();
  for (let i = 0; i < 6; ++i) {
    hash.insert(names[i], descs[i]);
  }
  console.log("we should see ", hash.get("k110"));
  hash.insert("phone", "9433120451"); // 这里计算的散列是冲突的，是为了测试冲突情况下的插入
  console.log("we have ", hash.get("k101"), "and", hash.get("phone"));
  
  hash.forEach(function(el, i) {
    console.log(el, i);
  });




//   4.4　散列的应用

// 4.4.1　数组去重

// 利用Hash key的唯一性来去重
let number = [2,3,4,2,5,6,4,88,1];
let hash = {};
number.forEach(function(el){
  hash["."+el] = el // 前面加一点是为了保证顺序
});
let ret = [];
Object.keys(hash).forEach(function(key){
  ret.push(hash[key]);
});

// 4.4.2　求只出现一次的数字

let number = [2,3,4,2,5,6,4,88,1];
let hash = {};
number.forEach(function(el){
  if(hash[el] ){
    hash[el].count ++;
  }else{
    hash[el] = {
      count: 1,
      data: el,
    }
  }
  
});
let ret = [];
Object.keys(hash).forEach(function(key){
  if(hash[key].count === 1){
    ret.push(hash[key].data);
  }
});

// 4.4.3　两数之和
// 不妨一边查找，一边存储数据，找到就返回它们俩的索引值，代码如下：

function twoSum(numbers,  target) {
    let hash = new Hash();
    for(let i = 0; i < numbers.length; i++){
      let el = numbers[i];
        if(hash.get(el) !== null){
          let index = hash.get(el);
          return [index, i];
        }else{
          hash.insert(target - el, i);// target - el可能在后面找到
      }
    }
  }
  twoSum([5, 75,25], 100);// 1,2 


